/**
 * 求数组中第L个数到第R个数的和（频繁查询，数据结构）
 */
public class L_R_Sum {
    public static void main(String[] args) {
        int[] arr = {3, 5, 3, 4, 5, 5, 5, 4, 7, 2, 6, 2, 4, 3, 8, 4, 9, 5, 1};
        //
//        int[][] array = table(arr);
//        showTable(array);
//        queryTable(array,0,1);
        //
        int[] h = getH(arr);
        showH(h);
        querySumByH(h, 9, 11);
    }

    /**
     * 前缀和数组实现
     * @param arr
     * @return
     */
    public static int[] getH(int[] arr) {
        int[] H = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            if (i == 0) {
                H[i] = arr[i];
            } else {
                H[i] = arr[i] + H[i - 1];
            }
        }
        return H;
    }

    public static void showH(int[] H) {
        for (int i = 0; i < H.length; i++) {
            System.out.print(H[i] + " ");
        }
        System.out.println();
    }

    public static void querySumByH(int[] H, int L, int R) {
        if (L == 0) {
            System.out.println(H[R]);
        } else {
            System.out.println(H[R] - H[L - 1]);
        }
    }

    /**
     * 二维数据表实现
     *
     * @param arr
     * @return
     */
    public static int[][] table(int[] arr) {
        int N = arr.length;
        int[][] array = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = i; j < N; j++) {
                if (i == j) {
                    array[i][j] = arr[i];
                } else {
                    array[i][j] = array[i][j - 1] + arr[j];
                }
            }
        }
        return array;
    }

    public static void showTable(int[][] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[0].length; j++) {
                System.out.print(array[i][j] + "\t");
            }
            System.out.println();
        }
    }

    public static void queryTable(int[][] array, int L, int R) {
        int sum = array[L][R];
        System.out.println(sum);
    }
}
